package algorithm;

public class leetcode_0213 {
    public int rob(int[] nums) {
        int len=nums.length;
        if(len==1) return nums[0];
        if(len==2) return Math.max(nums[0],nums[1]);
        int[] dp1=new int[len];
        int[] dp2=new int[len];
        dp1[0]=nums[0];
        dp1[1]=Math.max(nums[0],nums[1]);
        int max=0;
        dp(dp1,0,len-2,nums);
        dp2[1]=nums[1];
        dp2[2]=Math.max(nums[1],nums[2]);
        max=dp1[len-2];
        dp(dp2,1,len-1,nums);
        return Math.max(dp2[len-1],max);
    }
    public void dp(int[] dp,int start,int end,int [] nums){
        for(int i=start+2;i<=end;++i){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
    }
}
